
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>矩阵乘法加速 · Algorithm Notes</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="Avanti">
        
        
    
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-disqus/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-donate/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-plus/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-advanced-emoji/emoji-website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-emphasize/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-mermaid-gb3/mermaid/mermaid.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-tbfed-pagefooter/footer.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-terminal/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
        <link rel="stylesheet" href="../styles/website.css">
        
    


    

        
    
    
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="master-theorem.html" />
    
    
    <link rel="prev" href="../" />
    

    
    <link rel="stylesheet" href="../gitbook/gitbook-plugin-chart/c3/c3.min.css">
    <script src="../gitbook/gitbook-plugin-chart/c3/d3.min.js"></script>
    <script src="../gitbook/gitbook-plugin-chart/c3/c3.min.js"></script>
    

    <script src="../gitbook/gitbook-plugin-graph/d3.min.js"></script>
    <script src="../gitbook/gitbook-plugin-graph/function-plot.js"></script>    

    <style>
    @media only screen and (max-width: 640px) {
        .book-header .hidden-mobile {
            display: none;
        }
    }
    </style>
    <script>
        window["gitbook-plugin-github-buttons"] = {};
    </script>

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    算法导论
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.2" data-path="Strassen.html">
            
                <a href="Strassen.html">
            
                    
                    矩阵乘法加速
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="master-theorem.html">
            
                <a href="master-theorem.html">
            
                    
                    主定理证明
            
                </a>
            

            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >矩阵乘法加速</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div class="search-plus" id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <p>&#x3000;&#x3000;&#x8BBE;&#x77E9;&#x9635;<script type="math/tex; ">\Av = (a_{ij})</script>&#x548C;<script type="math/tex; ">\Bv = (b_{ij})</script>&#x662F;<script type="math/tex; ">n</script>&#x9636;&#x65B9;&#x9635;&#xFF0C;&#x4E58;&#x79EF;<script type="math/tex; ">\Cv = (c_{ij})</script>&#x4EA6;&#x662F;<script type="math/tex; ">n</script>&#x9636;&#x65B9;&#x9635;&#xFF0C;&#x5176;&#x4E2D;
\begin{align*}
    c_{ij} = \sum_{k \in [n]} a_{ik} b_{kj}
\end{align*}
&#x56E0;&#x6B64;&#x6309;&#x6807;&#x51C6;&#x7684;&#x77E9;&#x9635;&#x4E58;&#x6CD5;&#xFF0C;&#x8BA1;&#x7B97;<script type="math/tex; ">\Cv</script>&#x7684;&#x65F6;&#x95F4;&#x5F00;&#x9500;&#x4E3A;<script type="math/tex; ">\Omega(n^3)</script>&#xFF0C;&#x4E8B;&#x5B9E;&#x4E0A;&#x8FD9;&#x4E2A;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;&#x53EF;&#x4EE5;&#x6539;&#x8FDB;&#x7684;&#x3002;</p>
<h2 id="&#x5206;&#x6CBB;&#x9012;&#x5F52;"><a name="&#x5206;&#x6CBB;&#x9012;&#x5F52;" class="plugin-anchor" href="#&#x5206;&#x6CBB;&#x9012;&#x5F52;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x5206;&#x6CBB;&#x9012;&#x5F52;</h2>
<p>&#x3000;&#x3000;&#x8BBE;&#x8BA1;&#x7B97;<script type="math/tex; ">\Cv</script>&#x7684;&#x65F6;&#x95F4;&#x5F00;&#x9500;&#x4E3A;<script type="math/tex; ">T(n)</script>&#xFF0C;&#x5C06;&#x77E9;&#x9635;&#x5206;&#x6210;<script type="math/tex; ">2 \times 2 = 4</script>&#x5757;&#xFF0C;&#x7531;&#x5206;&#x5757;&#x77E9;&#x9635;&#x4E58;&#x6CD5;&#x6709;
\begin{align*}
    \begin{bmatrix}
        \Cv_{11} &amp; \Cv_{12} \\ \Cv_{21} &amp; \Cv_{22}
    \end{bmatrix} =
    \begin{bmatrix}
        \Av_{11} &amp; \Av_{12} \\ \Av_{21} &amp; \Av_{22}
    \end{bmatrix}
    \begin{bmatrix}
        \Bv_{11} &amp; \Bv_{12} \\ \Bv_{21} &amp; \Bv_{22}
    \end{bmatrix} =
    \begin{bmatrix}
        \Av_{11} \Bv_{11} + \Av_{12} \Bv_{21} &amp; \Av_{11} \Bv_{12} + \Av_{12} \Bv_{22} \\
        \Av_{21} \Bv_{11} + \Av_{22} \Bv_{21} &amp; \Av_{21} \Bv_{12} + \Av_{22} \Bv_{22}
    \end{bmatrix}
\end{align*}
&#x5176;&#x4E2D;&#x5305;&#x542B;<script type="math/tex; ">8</script>&#x4E2A;<script type="math/tex; ">n/2</script>&#x9636;&#x65B9;&#x9635;&#x76F8;&#x4E58;&#x3001;<script type="math/tex; ">4</script>&#x4E2A;<script type="math/tex; ">n/2</script>&#x9636;&#x65B9;&#x9635;&#x76F8;&#x52A0;&#xFF0C;&#x6CE8;&#x610F;&#x6BCF;&#x4E2A;<script type="math/tex; ">n/2</script>&#x9636;&#x65B9;&#x9635;&#x6709;<script type="math/tex; ">n^2/4</script>&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x56E0;&#x6B64;&#x5171;&#x9700;&#x8FDB;&#x884C;<script type="math/tex; ">n^2</script>&#x6B21;&#x52A0;&#x6CD5;&#xFF0C;&#x7EFC;&#x4E0A;&#x6709;&#x9012;&#x63A8;&#x5173;&#x7CFB;
\begin{align*}
    T(n) = 8 \cdot T(n/2) + c_1 n^2
\end{align*}
&#x5176;&#x4E2D;<script type="math/tex; ">c_1</script>&#x4E3A;&#x5355;&#x6B21;&#x52A0;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x5F00;&#x9500;&#x3002;&#x8BBE;<script type="math/tex; ">n = 2^k</script>&#xFF0C;&#x5219;
\begin{align*}
    T(2^k)               &amp; = 8^1 \cdot T(2^{k-1}) + 8^0 \cdot c_1 4^k     \\
    8^1 \cdot T(2^{k-1}) &amp; = 8^2 \cdot T(2^{k-2}) + 8^1 \cdot c_1 4^{k-1} \\
    8^2 \cdot T(2^{k-2}) &amp; = 8^3 \cdot T(2^{k-3}) + 8^2 \cdot c_1 4^{k-2} \\
                         &amp; \vdots                                         \\
    8^{k-1} \cdot T(2^1) &amp; = 8^k \cdot T(2^0) + 8^{k-1} \cdot c_1 4^1
\end{align*}
&#x6CE8;&#x610F;<script type="math/tex; ">8^k = n^3</script>&#xFF0C;<script type="math/tex; ">T(1) = c_2</script>&#x662F;&#x5355;&#x6B21;&#x4E58;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x5F00;&#x9500;&#xFF0C;&#x7D2F;&#x52A0;&#x53EF;&#x5F97;
\begin{align*}
    T(n) &amp; = c_2 n^3 + c_1 4^k + 2^1 \cdot c_1 4^k + 2^2 \cdot c_1 4^k + \cdots + 2^{k-1} \cdot c_1 4^k = c_2 n^3 + c_1 4^k \frac{1-2^k}{1-2} \\
         &amp; = c_2 n^3 + c_1 n^2 (n-1) = (c_2 + c_1) n^3 - c_1 n^2
\end{align*}
&#x5373;&#x76F4;&#x63A5;&#x5206;&#x6CBB;&#x9012;&#x5F52;&#x5E76;&#x4E0D;&#x80FD;&#x6539;&#x8FDB;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x3002;</p>
<h2 id="&#x57FA;&#x672C;&#x60F3;&#x6CD5;"><a name="&#x57FA;&#x672C;&#x60F3;&#x6CD5;" class="plugin-anchor" href="#&#x57FA;&#x672C;&#x60F3;&#x6CD5;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x57FA;&#x672C;&#x60F3;&#x6CD5;</h2>
<p>&#x3000;&#x3000;&#x8981;&#x60F3;&#x6539;&#x8FDB;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;&#x5FC5;&#x987B;&#x5F97;&#x51CF;&#x5C11;&#x5B50;&#x95EE;&#x9898;&#x7684;&#x4E2A;&#x6570;&#xFF0C;&#x5373;&#x4E58;&#x6CD5;&#x7684;&#x6B21;&#x6570;&#x3002;&#x5C06;&#x4E58;&#x79EF;&#x62C9;&#x76F4;&#xFF0C;&#x6613;&#x77E5;
\begin{align*}
    \begin{bmatrix}
        \Av_{11} \Bv_{11} + \Av_{12} \Bv_{21} \\
        \Av_{11} \Bv_{12} + \Av_{12} \Bv_{22} \\
        \Av_{21} \Bv_{11} + \Av_{22} \Bv_{21} \\
        \Av_{21} \Bv_{12} + \Av_{22} \Bv_{22}
    \end{bmatrix} =
    \begin{bmatrix}
        \Av_{11} &amp; \zerov   &amp; \Av_{12} &amp; \zerov   \\
        \zerov   &amp; \Av_{11} &amp; \zerov   &amp; \Av_{12} \\
        \Av_{21} &amp; \zerov   &amp; \Av_{22} &amp; \zerov   \\
        \zerov   &amp; \Av_{21} &amp; \zerov   &amp; \Av_{22}
    \end{bmatrix}
    \begin{bmatrix}
        \Bv_{11} \\ \Bv_{12} \\ \Bv_{21} \\ \Bv_{22}
    \end{bmatrix} = \widetilde{\Av}
    \begin{bmatrix}
        \Bv_{11} \\ \Bv_{12} \\ \Bv_{21} \\ \Bv_{22}
    \end{bmatrix}
\end{align*}
<span class="blue">&#x73B0;&#x5047;&#x8BBE;<script type="math/tex; ">\widetilde{\Av}</script>&#x53EF;&#x4EE5;&#x5206;&#x89E3;&#x6210;<script type="math/tex; ">m</script>&#x4E2A;&#x201C;&#x5757;&#x79E9;<script type="math/tex; ">1</script>&#x77E9;&#x9635;&#x201D;&#x7684;&#x548C;&#xFF1A;</span>
\begin{align} \label{eq: decomposition}
    \widetilde{\Av} =
    \begin{bmatrix}
        \Av_{11} &amp; \zerov   &amp; \Av_{12} &amp; \zerov   \\
        \zerov   &amp; \Av_{11} &amp; \zerov   &amp; \Av_{12} \\
        \Av_{21} &amp; \zerov   &amp; \Av_{22} &amp; \zerov   \\
        \zerov   &amp; \Av_{21} &amp; \zerov   &amp; \Av_{22}
    \end{bmatrix} = \sum_{i \in [m]}
    \begin{bmatrix}
        \Pv_{i1} \\ \Pv_{i2} \\ \Pv_{i3} \\ \Pv_{i4}
    \end{bmatrix} \Rv_i
    \begin{bmatrix}
        \Qv_{i1} \\ \Qv_{i2} \\ \Qv_{i3} \\ \Qv_{i4}
    \end{bmatrix}^\top
\end{align}
<span class="blue">&#x5176;&#x4E2D;<script type="math/tex; ">\Rv_i</script>&#x53EA;&#x7531;<script type="math/tex; ">\Av_{11}, \Av_{12}, \Av_{21}, \Av_{22}</script>&#x8FDB;&#x884C;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#x5F97;&#x5230;&#x4E14;<script type="math/tex; ">\Pv_{i1}, \ldots,\Pv_{i4}, \Qv_{i1}, \ldots, \Qv_{i4} \in \{ \pm \Iv, \zerov \}</script></span>&#x3002;&#x5219;
\begin{align*}
    \begin{bmatrix}
        \Av_{11} \Bv_{11} + \Av_{12} \Bv_{21} \\
        \Av_{11} \Bv_{12} + \Av_{12} \Bv_{22} \\
        \Av_{21} \Bv_{11} + \Av_{22} \Bv_{21} \\
        \Av_{21} \Bv_{12} + \Av_{22} \Bv_{22}
    \end{bmatrix} = \sum_{i \in [m]}
    \begin{bmatrix}
        \Pv_{i1} \\ \Pv_{i2} \\ \Pv_{i3} \\ \Pv_{i4}
    \end{bmatrix} \Rv_i
    \class{green}{\begin{bmatrix}
                   \Qv_{i1} \\ \Qv_{i2} \\ \Qv_{i3} \\ \Qv_{i4}
               \end{bmatrix}^\top
        \begin{bmatrix}
            \Bv_{11} \\ \Bv_{12} \\ \Bv_{21} \\ \Bv_{22}
        \end{bmatrix}} = \sum_{i \in [m]}
    \begin{bmatrix}
        \Pv_{i1} \\ \Pv_{i2} \\ \Pv_{i3} \\ \Pv_{i4}
    \end{bmatrix} \Rv_i \class{green}{\Sv_i} = \sum_{i \in [m]}
    \begin{bmatrix}
        \Pv_{i1} \\ \Pv_{i2} \\ \Pv_{i3} \\ \Pv_{i4}
    \end{bmatrix} \Tv_i
\end{align*}
&#x5176;&#x4E2D;<script type="math/tex; ">\Sv_i = \Qv_{i1} \Bv_{11} + \Qv_{i2} \Bv_{12} + \Qv_{i3} \Bv_{21} + \Qv_{i4} \Bv_{22}</script>&#x53EA;&#x7531;<script type="math/tex; ">\Bv_{11}, \Bv_{12}, \Bv_{21}, \Bv_{22}</script>&#x8FDB;&#x884C;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#x5F97;&#x5230;&#x3002;&#x8BA1;&#x7B97;&#x5168;&#x90E8;<script type="math/tex; ">m</script>&#x4E2A;<script type="math/tex; ">\Tv_i = \Rv_i \Sv_i</script>&#x4F1A;&#x4EA7;&#x751F;<script type="math/tex; ">m</script>&#x4E2A;&#x5B50;&#x95EE;&#x9898;&#x3002;&#x53C8;<script type="math/tex; ">\Pv_{i1}, \ldots, \Pv_{i4} \in \{ \pm \Iv, \zerov \}</script>&#xFF0C;&#x56E0;&#x6B64;
\begin{align*}
    \begin{bmatrix}
        \Av_{11} \Bv_{11} + \Av_{12} \Bv_{21} \\
        \Av_{11} \Bv_{12} + \Av_{12} \Bv_{22} \\
        \Av_{21} \Bv_{11} + \Av_{22} \Bv_{21} \\
        \Av_{21} \Bv_{12} + \Av_{22} \Bv_{22}
    \end{bmatrix} = \sum_{i \in [m]}
    \begin{bmatrix}
        \Pv_{i1} \\ \Pv_{i2} \\ \Pv_{i3} \\ \Pv_{i4}
    \end{bmatrix} \Tv_i =
    \begin{bmatrix}
        \Pv_{11} \Tv_1 + \cdots + \Pv_{m1} \Tv_m \\
        \Pv_{12} \Tv_1 + \cdots + \Pv_{m2} \Tv_m \\
        \Pv_{13} \Tv_1 + \cdots + \Pv_{m3} \Tv_m \\
        \Pv_{14} \Tv_1 + \cdots + \Pv_{m4} \Tv_m
    \end{bmatrix}
\end{align*}
&#x53EA;&#x7531;<script type="math/tex; ">\Tv_1, \ldots, \Tv_m</script>&#x8FDB;&#x884C;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#x5F97;&#x5230;&#x3002;&#x7EFC;&#x4E0A;&#xFF0C;&#x5173;&#x952E;&#x5C31;&#x662F;&#x5982;&#x4F55;&#x4F7F;&#x5F0F;(\ref{eq: decomposition})&#x4E2D;&#x7684;<script type="math/tex; ">m < 8</script>&#x3002;</p>
<p>&#x3000;&#x3000;&#x4E0B;&#x9762;&#x7ED9;&#x51FA;&#x4E00;&#x4E2A;<script type="math/tex; ">m = 7</script>&#x7684;&#x5206;&#x89E3;&#x65B9;&#x6CD5;&#xFF0C;&#x9996;&#x5148;&#x53BB;&#x6389;&#x5DE6;&#x4E0A;&#x7684;<script type="math/tex; ">\Av_{11}</script>&#x548C;&#x53F3;&#x4E0B;&#x7684;<script type="math/tex; ">\Av_{22}</script>
\begin{align*}
    \widetilde{\Av} -
     &amp;
    \begin{bmatrix}
        \Av_{11} &amp; \zerov &amp; \Av_{11} &amp; \zerov \\
        \zerov   &amp; \zerov &amp; \zerov   &amp; \zerov \\
        \Av_{11} &amp; \zerov &amp; \Av_{11} &amp; \zerov \\
        \zerov   &amp; \zerov &amp; \zerov   &amp; \zerov
    \end{bmatrix} -
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \zerov &amp; \zerov \\ \zerov &amp; \Av_{22} &amp; \zerov &amp; \Av_{22} \\ \zerov &amp; \zerov &amp; \zerov &amp; \zerov \\ \zerov &amp; \Av_{22} &amp; \zerov &amp; \Av_{22}
    \end{bmatrix} =
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \Av_{12} - \Av_{11} &amp; \zerov \\ \zerov &amp; \Av_{11} - \Av_{22} &amp; \zerov &amp; \Av_{12} - \Av_{22} \\ \Av_{21} - \Av_{11} &amp; \zerov &amp; \Av_{22} - \Av_{11} &amp; \zerov \\ \zerov &amp; \Av_{21} - \Av_{22} &amp; \zerov &amp; \zerov
    \end{bmatrix} \\
     &amp; =
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \zerov &amp; \zerov \\ \zerov &amp; \Av_{11} - \Av_{22} &amp; \Av_{11} - \Av_{22} &amp; \zerov \\ \zerov &amp; \Av_{22} - \Av_{11} &amp; \Av_{22} - \Av_{11} &amp; \zerov \\ \zerov &amp; \zerov &amp; \zerov &amp; \zerov
    \end{bmatrix} +
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \Av_{12} - \Av_{11} &amp; \zerov \\ \zerov &amp; \zerov &amp; \Av_{22} - \Av_{11} &amp; \Av_{12} - \Av_{22} \\ \Av_{21} - \Av_{11} &amp; \Av_{11} - \Av_{22} &amp; \zerov &amp; \zerov \\ \zerov &amp; \Av_{21} - \Av_{22} &amp; \zerov &amp; \zerov
    \end{bmatrix} \\
     &amp; = \begin{bmatrix}
             \zerov &amp; \zerov &amp; \zerov &amp; \zerov \\ \zerov &amp; \Av_{11} - \Av_{22} &amp; \Av_{11} - \Av_{22} &amp; \zerov \\ \zerov &amp; \Av_{22} - \Av_{11} &amp; \Av_{22} - \Av_{11} &amp; \zerov \\ \zerov &amp; \zerov &amp; \zerov &amp; \zerov
         \end{bmatrix} +
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \zerov              &amp; \zerov              \\
        \zerov &amp; \zerov &amp; \Av_{22} - \Av_{12} &amp; \Av_{12} - \Av_{22} \\
        \zerov &amp; \zerov &amp; \zerov              &amp; \zerov              \\
        \zerov &amp; \zerov &amp; \zerov              &amp; \zerov
    \end{bmatrix} +
    \begin{bmatrix}
        \zerov &amp; \zerov &amp; \Av_{12} - \Av_{11} &amp; \zerov \\
        \zerov &amp; \zerov &amp; \Av_{12} - \Av_{11} &amp; \zerov \\
        \zerov &amp; \zerov &amp; \zerov              &amp; \zerov \\
        \zerov &amp; \zerov &amp; \zerov              &amp; \zerov
    \end{bmatrix}                                                                                                                                                                                \\
     &amp; \qquad +
    \begin{bmatrix}
        \zerov              &amp; \zerov              &amp; \zerov &amp; \zerov \\
        \zerov              &amp; \zerov              &amp; \zerov &amp; \zerov \\
        \Av_{21} - \Av_{11} &amp; \Av_{11} - \Av_{21} &amp; \zerov &amp; \zerov \\
        \zerov              &amp; \zerov              &amp; \zerov &amp; \zerov
    \end{bmatrix} +
    \begin{bmatrix}
        \zerov &amp; \zerov              &amp; \zerov &amp; \zerov \\
        \zerov &amp; \zerov              &amp; \zerov &amp; \zerov \\
        \zerov &amp; \Av_{21} - \Av_{22} &amp; \zerov &amp; \zerov \\
        \zerov &amp; \Av_{21} - \Av_{22} &amp; \zerov &amp; \zerov
    \end{bmatrix}                                                                                                                                                                                \\
     &amp; =
    \begin{bmatrix}
        \Iv \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix} \Av_{11}
    \begin{bmatrix}
        \Iv \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix}^\top +
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \Iv
    \end{bmatrix} \Av_{22}
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \Iv
    \end{bmatrix}^\top +
    \begin{bmatrix}
        \zerov \\ \Iv \\ -\Iv \\ \zerov
    \end{bmatrix} (\Av_{11} - \Av_{22})
    \begin{bmatrix}
        \zerov \\ \Iv \\ \Iv \\ \zerov
    \end{bmatrix}^\top +
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \zerov
    \end{bmatrix} (\Av_{22} - \Av_{12})
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ -\Iv
    \end{bmatrix}^\top                                                                                                                                                                                                \\
     &amp; \qquad +
    \begin{bmatrix}
        \Iv \\ \Iv \\ \zerov \\ \zerov
    \end{bmatrix} (\Av_{12} - \Av_{11})
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix}^\top +
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix} (\Av_{21} - \Av_{11})
    \begin{bmatrix}
        \Iv \\ -\Iv \\ \zerov \\ \zerov
    \end{bmatrix}^\top +
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ \Iv
    \end{bmatrix} (\Av_{21} - \Av_{22})
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \zerov
    \end{bmatrix}^\top
\end{align*}</p>
<h2 id="&#x7B97;&#x6CD5;&#x5B9E;&#x73B0;"><a name="&#x7B97;&#x6CD5;&#x5B9E;&#x73B0;" class="plugin-anchor" href="#&#x7B97;&#x6CD5;&#x5B9E;&#x73B0;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x7B97;&#x6CD5;&#x5B9E;&#x73B0;</h2>
<p>&#x3000;&#x3000;&#x6839;&#x636E;&#x4E0A;&#x9762;&#x7684;&#x5206;&#x89E3;&#x6613;&#x77E5;&#x8BA1;&#x7B97;
\begin{align*}
    \begin{bmatrix}
        \Sv_1 \\ \Sv_2 \\ \Sv_3 \\ \Sv_4 \\ \Sv_5 \\ \Sv_6 \\ \Sv_7
    \end{bmatrix} =
    \begin{bmatrix}
        \Iv    &amp; \zerov &amp; \Iv    &amp; \zerov \\
        \zerov &amp; \Iv    &amp; \zerov &amp; \Iv    \\
        \zerov &amp; \Iv    &amp; \Iv    &amp; \zerov \\
        \zerov &amp; \zerov &amp; \Iv    &amp; -\Iv   \\
        \zerov &amp; \zerov &amp; \Iv    &amp; \zerov \\
        \Iv    &amp; -\Iv   &amp; \zerov &amp; \zerov \\
        \zerov &amp; \Iv    &amp; \zerov &amp; \zerov
    \end{bmatrix}
    \begin{bmatrix}
        \Bv_{11} \\ \Bv_{12} \\ \Bv_{21} \\ \Bv_{22}
    \end{bmatrix} =
    \begin{bmatrix}
        \Bv_{11} + \Bv_{21} \\ \Bv_{12} + \Bv_{22} \\ \Bv_{12} + \Bv_{21} \\ \Bv_{21} - \Bv_{22} \\ \Bv_{21} \\ \Bv_{11} - \Bv_{12} \\ \Bv_{12}
    \end{bmatrix}, \quad
    \begin{bmatrix}
        \Rv_1 \\ \Rv_2 \\ \Rv_3 \\ \Rv_4 \\ \Rv_5 \\ \Rv_6 \\ \Rv_7
    \end{bmatrix} =
    \begin{bmatrix}
        \Av_{11} \\ \Av_{22} \\ \Av_{11} - \Av_{22} \\ \Av_{22} - \Av_{12} \\ \Av_{12} - \Av_{11} \\ \Av_{21} - \Av_{11} \\ \Av_{21} - \Av_{22}
    \end{bmatrix}
\end{align*}
&#x5171;&#x4F1A;&#x4EA7;&#x751F;<script type="math/tex; ">10</script>&#x6B21;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#xFF0C;&#x8BA1;&#x7B97;<script type="math/tex; ">\Tv_1 = \Rv_1 \Sv_1, \ldots, \Tv_7 = \Rv_7 \Sv_7</script>&#x5171;&#x4F1A;&#x4EA7;&#x751F;<script type="math/tex; ">7</script>&#x4E2A;&#x5B50;&#x95EE;&#x9898;&#xFF0C;&#x6700;&#x540E;&#x8BA1;&#x7B97;
\begin{align*}
    \begin{bmatrix}
        \Av_{11} \Bv_{11} + \Av_{12} \Bv_{21} \\
        \Av_{11} \Bv_{12} + \Av_{12} \Bv_{22} \\
        \Av_{21} \Bv_{11} + \Av_{22} \Bv_{21} \\
        \Av_{21} \Bv_{12} + \Av_{22} \Bv_{22}
    \end{bmatrix}
     &amp; =
    \begin{bmatrix}
        \Iv \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix} \Tv_1 +
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \Iv
    \end{bmatrix} \Tv_2 +
    \begin{bmatrix}
        \zerov \\ \Iv \\ -\Iv \\ \zerov
    \end{bmatrix} \Tv_3 +
    \begin{bmatrix}
        \zerov \\ \Iv \\ \zerov \\ \zerov
    \end{bmatrix} \Tv_4 +
    \begin{bmatrix}
        \Iv \\ \Iv \\ \zerov \\ \zerov
    \end{bmatrix} \Tv_5 +
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ \zerov
    \end{bmatrix} \Tv_6 +
    \begin{bmatrix}
        \zerov \\ \zerov \\ \Iv \\ \Iv
    \end{bmatrix} \Tv_7 \\
     &amp; =
    \begin{bmatrix}
        \Tv_1 + \Tv_5 \\ \Tv_2 + \Tv_3 + \Tv_4 + \Tv_5 \\ \Tv_1 - \Tv_3 + \Tv_6 + \Tv_7 \\ \Tv_2 + \Tv_7
    \end{bmatrix}
\end{align*}
&#x5171;&#x4F1A;&#x4EA7;&#x751F;<script type="math/tex; ">8</script>&#x6B21;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#x3002;</p>
<p>&#x3000;&#x3000;&#x7EFC;&#x4E0A;&#xFF0C;&#x4E00;&#x5171;&#x4F1A;&#x4EA7;&#x751F;<script type="math/tex; ">7</script>&#x4E2A;&#x5B50;&#x95EE;&#x9898;&#x548C;<script type="math/tex; ">18</script>&#x6B21;&#x52A0;&#x51CF;&#x8FD0;&#x7B97;&#xFF0C;&#x6B64;&#x65F6;&#x9012;&#x63A8;&#x5173;&#x7CFB;&#x53D8;&#x6210;
\begin{align*}
    T(n) = 7 \cdot T(n/2) + \frac{18}{4} c_1 n^2
\end{align*}
&#x8BBE;<script type="math/tex; ">n = 2^k</script>&#xFF0C;&#x5219;
\begin{align*}
    T(2^k)               &amp; = 7^1 \cdot T(2^{k-1}) + \frac{18}{4} c_1 4^k         \\
    7^1 \cdot T(2^{k-1}) &amp; = 7^2 \cdot T(2^{k-2}) + 7^1 \frac{18}{4} c_1 4^{k-1} \\
    7^2 \cdot T(2^{k-2}) &amp; = 7^3 \cdot T(2^{k-3}) + 7^2 \frac{18}{4} c_1 4^{k-2} \\
                         &amp; \vdots                                                \\
    7^{k-1} \cdot T(2^1) &amp; = 7^k \cdot T(2^0) + 7^{k-1} \frac{18}{4} c_1 4^1
\end{align*}
&#x6CE8;&#x610F;<script type="math/tex; ">7^k = (2^{\lg 7})^k = (2^k)^{\lg 7} = n^{\lg 7} \approx n^{2.81}</script>&#xFF0C;
&#x7D2F;&#x52A0;&#x53EF;&#x5F97;
\begin{align*}
    T(n) = c_2 n^{\lg 7} + \frac{18}{4} c_1 4^k \frac{1-(7/4)^k}{1-(7/4)} = c_2 n^{\lg 7} + 6 c_1 (n^{\lg 7} - n^2) = \left( c_2 + 6 c_1 \right) n^{\lg 7} - 6 c_1 n^2
\end{align*}</p>
<footer class="page-footer"><span class="copyright">Copyright &#xA9; Avanti 2022 all right reserved&#xFF0C;powered by Gitbook</span><span class="footer-modification">&#x6587;&#x4EF6;&#x6700;&#x540E;&#x4FEE;&#x6539;&#x65F6;&#x95F4;&#xFF1A;
2022-03-10 23:10:47
</span></footer>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="../" class="navigation navigation-prev " aria-label="Previous page: 算法导论">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="master-theorem.html" class="navigation navigation-next " aria-label="Next page: 主定理证明">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"矩阵乘法加速","level":"1.2","depth":1,"next":{"title":"主定理证明","level":"1.3","depth":1,"path":"posts/master-theorem.md","ref":"posts/master-theorem.md","articles":[]},"previous":{"title":"算法导论","level":"1.1","depth":1,"path":"README.md","ref":"README.md","articles":[]},"dir":"ltr"},"config":{"plugins":["mathjax@git+https://github.com/CHN-beta/plugin-mathjax.git#update_cdn","splitter","disqus","donate","github","github-buttons","copy-code-button","-lunr","-search","search-plus","advanced-emoji","emphasize","mermaid-gb3","puml","graph","chart","-sharing","sharing-plus","tbfed-pagefooter","anchors","terminal"],"root":".","styles":{"website":"styles/website.css"},"pluginsConfig":{"tbfed-pagefooter":{"copyright":"Copyright &copy Avanti 2022","modify_label":"文件最后修改时间：","modify_format":"YYYY-MM-DD HH:mm:ss"},"disqus":{"useIdentifier":false,"shortName":"algorithm-notes"},"emphasize":{},"github":{"url":"https://github.com/Avanti1980"},"puml":{},"splitter":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"graph":{},"donate":{"alipay":"https://gitee.com/avanti1980/notes-on-math/raw/master/img/zfb.jpg","alipayText":"支付宝","button":"赏","title":"","wechat":"https://gitee.com/avanti1980/notes-on-math/raw/master/img/wx.jpg","wechatText":"微信"},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"mermaid-gb3":{},"github-buttons":{},"mathjax":{"forceSVG":false,"version":"2.7.1"},"copy-code-button":{},"advanced-emoji":{"embedEmojis":false},"sharing":{"qq":true,"douban":true,"facebook":true,"weibo":true,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":true,"vk":false,"pocket":false,"google":true,"viber":false,"stumbleupon":false,"qzone":true,"linkedin":true},"terminal":{"copyButtons":true,"fade":false,"style":"flat"},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"chart":{"type":"c3"},"search-plus":{}},"theme":"default","author":"Avanti","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"Algorithm Notes","language":"zh-hans","output.name":"site","gitbook":"3.2.3","description":"算法讲义"},"file":{"path":"posts/Strassen.md","mtime":"2022-03-10T15:10:47.819Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2022-03-10T17:23:54.764Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-mathjax/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="https://cdnjs.cloudflare.com/ajax/libs/URI.js/1.16.1/URI.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-disqus/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-donate/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-github/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-github-buttons/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-plus/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-plus/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-mermaid-gb3/book/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-terminal/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    <script src="../gitbook/gitbook-plugin-mermaid-gb3/mermaid/mermaid.min.js"></script>

    </body>
</html>

